#include<bits/stdc++.h>
using namespace std;

struct Node {
	int val;
	Node* left;
	Node* right;
	int height;
	Node(int val_) :val{ val_ }, height{0},left{nullptr},right{nullptr}{}
	Node(int val_,Node* left_,Node* right_):val{val_},left{left_},right{right_}{}
};

int getheight(Node* root) {
	if (root == nullptr) return -1;
	else return root->height;
}

Node* LL(Node* root) {
	auto lt = root->left;
	root->left = lt->right;
	lt->right = root;
	root->height = max(getheight(root->left),getheight(root->right)) + 1;
	lt->height = max(getheight(lt->left),root->height)+1;
	return lt;
}
Node* RR(Node* root) {
	auto rt = root->right;
	root->right = rt->left;
	rt->left = root;
	root->height = max(getheight(root->left),getheight(root->right)) + 1;
	rt->height = max( getheight(rt->right),root->height)+ 1;
	return rt;
}
Node* LR(Node* root) {
	root->left = RR(root->left);
	return LL(root);
}
Node* RL(Node* root) {
	root->right = LL(root->right);
	return RR(root);
}
//
Node* insert(Node* root,const int v) {
	if (root == nullptr) {
		root = new Node{ v };
		printf("%d ",v);
	}
	else if (v < root->val) {
		root->left = insert(root->left, v);
		if (getheight(root->left) - getheight(root->right) == 2) {
			if (v < root->left->val) {
				root = LL(root);
			}
			else if (v > root->left->val) {
				root = LR(root);
			}
		}
	}
	else if (v > root->val) {
		root->right = insert(root->right, v);
		if (getheight(root->right) - getheight(root->left) == 2) {
			if (v > root->right->val) {
				root = RR(root);
			}
			else if (v < root->right->val) {
				root = RL(root);
			}
		}
	}
	root->height = max(getheight(root->left), getheight(root->right)) + 1;
	return root;
}

int T,n,num;
int main(){
	scanf("%d",&T);
	for(int i=0;i<T;i++){
		scanf("%d",&n);
		Node* root=nullptr;
		for(int j=0;j<n;j++){
			scanf("%d",&num);
			root=insert(root,num);
		};
		printf("\n");
	}
	return 0;
}


//#include<bits/stdc++.h>
//using namespace std;
//
//int T,n,num;
//class Node{
//public:
//	int val,h;
//	Node* left;
//	Node* right;
//	Node(int val_){
//		val=val_;left=nullptr;right=nullptr;
//	}
//};
//
//bool tag;
//Node* insert(Node* root,const int val){
//	if(!root){
//		root=new Node{val};
//		cout<<num<<' ';
//	}
//	else if(root->val<val){
//		root->right=insert(root->right,val);
//	}
//	else if(root->val>val){
//		root->left=insert(root->left,val);
//	}
//	return root;
//}
//
//int main(){
//	cin>>T;
//	for(int i=0;i<T;i++){
//		cin>>n;
//		Node* root=nullptr;
//		//unordered_map<int,bool> mymap;
//		for(int j=0;j<n;j++){
//			cin>>num;
//			tag=false;
//			root=insert(root,num);
////			if(!tag){
////				cout<<num<<' ';
////			}
//			//HaXi table
////			if(!mymap.count(num)){
////				cout<<num<<' ';
////				mymap[num]=true;
////			}
//		}
//		cout<<endl;
//	}
//	return 0;
//}
